package com.codingvip.tree.visit.visitInterate;

import com.codingvip.tree.TreeNode;

import javax.xml.bind.annotation.adapters.CollapsedStringAdapter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @Author Tony.Han
 * @Created at 2020/4/5 5:13 下午
 * Desc:
 */
public class InOrderTraver {
    //    def inorderTraversal(self, root: TreeNode) -> List[int]:
//    WHITE, GRAY = 0, 1
//    res = []
//    stack = [(WHITE, root)]
//            while stack:
//    color, node = stack.pop()
//            if node is None: continue
//            if color == WHITE:
//            stack.append((WHITE, node.right))
//            stack.append((GRAY, node))
//            stack.append((WHITE, node.left))
//            else:
//            res.append(node.val)
//            return res

    public static void main(String[] args) {


        List<Integer> nums = Arrays.asList(1, 2, 3, 4, 5);
        TreeNode treeNode = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        treeNode.left = node2;
        treeNode.right = node3;

        node2.left = node4;
        node2.right = node5;

        InOrderTraver inOrderTraver = new InOrderTraver();
//        node3.left = node2;
        List<Integer> result = inOrderTraver.inorderTraversal(treeNode);
        for (Integer integer : result) {
            System.out.println(integer);

        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack stack = new Stack();
        stack.push(new ColorTreeNode(root, 0));
        while (!stack.isEmpty()) {
            ColorTreeNode node = (ColorTreeNode) stack.pop();
            if (node.isGray()) {
                res.add(node.value.val);
            } else {

                if (node.value.right != null) {
                    stack.push(addWhiteTreeNode(node.value.right));
                }
                stack.push(addGrayTreeNode(node.value));
                if (node.value.left != null) {
                    stack.push(addWhiteTreeNode(node.value.left));
                }

            }


        }

        return res;

    }

    ColorTreeNode addGrayTreeNode(TreeNode value) {
        return new ColorTreeNode(value, 1);

    }

    ColorTreeNode addWhiteTreeNode(TreeNode value) {
        return new ColorTreeNode(value, 0);
    }

    class ColorTreeNode {
        TreeNode value;
        int clolor;

        public ColorTreeNode(TreeNode value, int clolor) {
            this.value = value;
            this.clolor = clolor;
        }

        public boolean isGray() {
            return this.clolor == 1;
        }
    }

}
